package 数据结构;

import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;

/**
 * 跳表的java实现
 */
public class SkipList {

    /**
     * 允许最大层数
     */
    private static final int MAX_LEVEL = 16;
    /**
     * 目前最大层数
     */
    private int levelCount = 1;

    /**
     * 获取随机层数中每次增加层数的概率
     */
    private final static double p = 0.25;

    /**
     * 带头链表
     */
    private Node head = new Node(MAX_LEVEL);
    private Random r = new Random();

    /**
     * 得到一个随机层数
     * @return
     */
    private int getRandomLevel(){
        int level = 1;
        while (r.nextDouble() < p && level < MAX_LEVEL){
            level++;
        }
        return level;
    }

    public void  insert(int val){
        insert(val,0 );
    }

    /**
     * 插入
     * @param val
     * @param level
     */
    public void insert(int val,int level){
        if (level==0){
            level = getRandomLevel();
        }
        if (level > levelCount){
            levelCount = level;
        }
        Node newNode = new Node(level);
        newNode.data = val;
        Node[] updates = new Node[level];

        Node p = this.head;

        //找出新节点所有要插入的位置
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < val){
                p = p.forwards[i];
            }
            if (i < level){
                updates[i] = p;
            }
        }
        //插入进去
        for (int i = 0; i < level; i++) {
            newNode.forwards[i] = updates[i].forwards[i];
            updates[i].forwards[i] = newNode;
        }
    }


    /**
     * 打印
     */
    public void printAll_beautiful() {
        Node p = head;
        Node[] c = p.forwards;
        Node[] d = c;
        int maxLevel = c.length;
        for (int i = levelCount - 1; i >= 0; i--) {
            do {
                System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
            } while (d[i] != null && (d = d[i].forwards)[i] != null);
            System.out.println();
            d = c;
        }
    }

    /**
     * 统计每层有多少个
     */
    public void tongji(){
        for (int i = 1; i < levelCount; i++) {
            int num = 0;
            Node p = head;
            while ((p = p.forwards[i]) != null){
                num++;
            }
            System.out.println("第"+i+"层有"+num+"个数");
        }
    }

    /**
     * 根据分数区间查询数据集合[start,end]
     */
    public List<Integer> revrangebyscore(int start,int end){
        Node p = this.head;
        int i = levelCount - 1;
        boolean flag = true;
        /**
         * 找到离start最近的节点
         */
        while (i >= 0 && flag){
            while (p.forwards[i] != null){
                int data = p.forwards[i].data;
                if (data > start){
                    break;
                }else if (data == start){
                    flag = false;
                    p = p.forwards[i];
                    break;
                }
                p = p.forwards[i];
            }
            i--;
        }
        List<Integer> list = new ArrayList();
        list.add(p.data);
        while ((p = p.forwards[0]) != null && p.data <= end){
            list.add(p.data);
        }
        return list;
    }

    /**
     * 删除一个节点
     * @param val
     */
    public void delete(int val) {
        Node[] cur = null;
        Node[] pre = null;

        Node p = this.head;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.forwards[i] != null){
                Node forward = p.forwards[i];
                int data = forward.data;
                if (data > val){
                    break;
                }else if (data == val){
                    if (cur == null){

                        cur = new Node[i+1];
                        pre = new Node[i+1];
                    }
                    cur[i] = forward;
                    pre[i] = p;
                    break;
                }
                p = forward;
            }
        }
        if (cur == null){
            System.out.println("不存在该元素");
            throw new RuntimeException("不存在该元素");
        }

        for (int i = 0; i < cur.length; i++) {
            pre[i].forwards[i] = cur[i].forwards[i];
            cur[i] = null;
        }



    }





    public class Node{
        private int data ;

        private Node[] forwards;



        public Node(int level){
            forwards = new Node[level];
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{ data: ");
            builder.append(data);
            return builder.toString();
        }



    }

    public static void main(String[] args) {
        ArrayList<Integer> al = new ArrayList();
        SkipList list = new SkipList();
        for (int i = 1; i <= 10; i++) {
            al.add(i);
        }
        Collections.shuffle(al);
        for (int i = 0; i < al.size(); i++) {
            list.insert(al.get(i) );
        }
        list.printAll_beautiful();
        list.delete(1);
        list.printAll_beautiful();
        //list.delete(11);
        //list.printAll_beautiful();
        //ConcurrentSkipListMap
    }
}
